package com.terry.test3;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

/**
 * 标题：二叉树的广度优先遍历 
 *
 * 有一个二叉树，每一个节点都有一个大写字母标识(最多26个节点）。
 *
 * 现有两组字母，分别表示后序遍历（左->右->父）和中序遍历（左->父->右）的结果，请输出层次遍历的结果。
 *
 * 输入描述:
 *
 * 输入为两个字符串，分别是二叉树的后续遍历和中序遍历结果。
 *
 * 输出描述:
 *
 * 输出二叉树的层次遍历结果。
 *
 * 示例1
 *
 * 输入
 *
 * CBEFDA CBAEDF
 *
 *
 * 输出
 *
 * ABDCEF
 *
 * 说明
 *
 * 二叉树为：
 *
 * A
 *
 * / \
 *
 * B  D
 *
 * / / \
 *
 * C E  F
 *
 * 作者：一个小白白白
 * 链接：https://www.jianshu.com/p/b398e38a2fd1
 * 来源：简书
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */
class TreeNode{
    public char c;
    public TreeNode left;
    public TreeNode right;
}

public class Title26 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        while(scanner.hasNextLine()){
           String[] lines = scanner.nextLine().split(" ");
           //后续 lines[0],中序 lines[1]
           TreeNode root = buildTree(lines[0],lines[1]);
            printTree(root);
        }
    }

    public static void printTree(TreeNode root){
        Deque<TreeNode> deque = new ArrayDeque<>();
        deque.addLast(root);
        while(!deque.isEmpty()){
            TreeNode treeNode = deque.removeFirst();
            if(treeNode.left!=null){
                deque.addLast(treeNode.left);
            }
            if(treeNode.right!=null){
                deque.addLast(treeNode.right);
            }
            System.out.print(treeNode.c);
        }
        System.out.println();
    }
    // 后     中
    //CBEFDA CBAEDF
    public static TreeNode buildTree(String hStr,String zStr){
        if(hStr.isEmpty()){
            return null;
        }
        TreeNode root = new TreeNode();
        root.c = hStr.charAt(hStr.length()-1);
        int index = zStr.indexOf(root.c);
        if(hStr.length()==1){
            return root;
        }
        root.left = buildTree(hStr.substring(0,index),zStr.substring(0,index));
        root.right = buildTree(hStr.substring(index,hStr.length()-1),zStr.substring(index+1));
        return root;
    }

}
